package _dp;

import org.junit.Assert;
import org.junit.Test;

/*
https://leetcode.cn/problems/unique-paths-ii/description/

63. 不同路径 II
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。

示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2

示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
 */
public class leetcode_63 {
    @Test
    public void test_1() {
        int actual = uniquePathsWithObstacles(new int[][]{
                {0, 0, 0}, {0, 1, 0}, {0, 0, 0}
        });
        int expect = 2;
        Assert.assertEquals(expect, actual);
    }

    @Test
    public void test_2() {
        int actual = uniquePathsWithObstacles(new int[][]{
                {0, 1}, {0, 0}
        });
        int expect = 1;
        Assert.assertEquals(expect, actual);
    }

    @Test
    public void test_3() {
        int actual = uniquePathsWithObstacles(new int[][]{
                {0, 1, 0, 0}
        });
        int expect = 0;
        Assert.assertEquals(expect, actual);
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /*
        动态规划
         */

        int row = obstacleGrid.length;
        int column = obstacleGrid[0].length;

        // 1 数组
        // 2 递推公式 dp[i][j] = dp[i-1][j] + dp[i][j-1]，gradie[i][j]!=1
        // 3 初始化数组
        // dp[0 .. i][0] = 1 ,gradie[i][j]!=1
        // dp[0][0..j] = 1,gradie[i][j]!=1
        // 4 遍历
        // 5 打印数组

        // 开始位置和 结束为止为障碍物
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][column - 1] == 1) {
            return 0;
        }

        int[][] dp = new int[row][column];
        for (int i = 0; i < row && obstacleGrid[i][0] != 1; i++) { // 不能是障碍物
            dp[i][0] = 1;
        }
        for (int j = 0; j < column && obstacleGrid[0][j] != 1; j++) { // 不能是障碍物
            dp[0][j] = 1;
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < column; j++) {
                if (obstacleGrid[i][j] != 1) {  // 不能是障碍物
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    // System.out.println("dp["+i+"]["+j+"]="+dp[i][j]);
                }
            }
        }
        return dp[row - 1][column - 1];
    }
}